public class Test {
    //递归求 N 的阶乘
    public static int fact(int n){
        if(n == 1){
            return  1;
        }
        return n * fact(n-1);
    }

    //递归求 1 + 2 + 3 + ... + 10
    public static int sum(int n){
        if(n == 1){
            return 1;
        }
        return n + sum(n-1);
    }

    //按顺序打印一个数字的每一位(例如 1234 打印出 1 2 3 4)    （递归）
    public static void print(int n){
        if(n <= 9){
            System.out.println(n);
            return;
        }
        print(n / 10);
        System.out.println(n % 10);
    }
    //打印 4 3 2 1 只需调换两行代码的顺序！！！！！
//    public static void print(int n){
//        if(n <= 9){
//            System.out.println(n);
//            return;
//        }
//        System.out.println(n % 10);
//        print(n / 10);
//    }

    //写一个递归方法，输入一个非负整数，返回组成它的数字之和
    public static int numSum(int n){
        if(n <= 9){
            return n;
        }
        return (n % 10) + numSum(n / 10);
    }

    //递归求斐波那契数列的第 N 项
    // 1 1 2 3 5 8 13 21....
    public static int fib(int n){
        if(n == 1 || n == 2){
            return 1;
        }
        return fib(n-1) + fib(n-2);
    }

    //递归求解汉诺塔问题
    public static int count = 0;
    public static void Hanoi(int n,char posA,char posB,char posC){
        if(n == 1){
            move(posA,posC);
            return;
        }
        Hanoi(n-1,posA,posC,posB); //从A移到B，借助C
        move(posA,posC); //最后一个可以移到C了
        Hanoi(n-1,posB,posA,posC); //从B移到C，借助A
    }
    public static void move(char posSrc,char posDest){
        count++;
        System.out.print(posSrc + "->" + posDest + " ");
    }

    public static void main(String[] args) {
        //int ret = fact(5);
        //int ret = sum(10);
        //print(1234);
        //int ret = numSum(1234);
        //int ret = fib(7);
        //System.out.println(ret);
        Hanoi(3,'A','B','C');
        System.out.println(count);
    }
}